package problem295;

import java.util.PriorityQueue;

//295.数据流中的中位数
//https://leetcode.cn/problems/find-median-from-data-stream/

class MedianFinder {
    PriorityQueue<Integer> lqueue;
    PriorityQueue<Integer> rqueue;

    public MedianFinder() {
        lqueue = new PriorityQueue<>((a,b)->b-a);
        rqueue = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        if(lqueue.size() == rqueue.size()) {
            if(lqueue.isEmpty() || num <= lqueue.peek()) {
                lqueue.add(num);
            }else {
                rqueue.add(num);
                lqueue.add(rqueue.poll());
            }
        }else {
            if(num > lqueue.peek()) {
                rqueue.add(num);
            }else {
                lqueue.add(num);
                rqueue.add(lqueue.poll());
            }
        }
    } 
    
    public double findMedian() {
        if(lqueue.size() > rqueue.size()) return lqueue.peek();
        else return (lqueue.peek() + rqueue.peek())/2.0;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

 /*

2 3 4
2 3

 */